/* Implements linked_list abstract data type. */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "linked_list.h"

typedef struct linked_list_link_data_t *linked_list_link_t;

/* Define link*/
struct linked_list_link_data_t {
  linked_list_element_t k;
  linked_list_element_t e;
  linked_list_link_t next;
};

struct linked_list_data_t {
  linked_list_link_t head;
};

linked_list_t
linked_list_create()
{
  linked_list_t l = (linked_list_t)malloc(sizeof(struct linked_list_data_t));
  l->head = NULL;
  return l;
}

/* Private */
static linked_list_link_t
linked_list_new_element(linked_list_element_t k,linked_list_element_t e)
{
  linked_list_link_t llt = (linked_list_link_t)malloc(sizeof(struct linked_list_link_data_t));
  llt->e  = e;
  llt->k = k;
  llt->next = NULL;
  return llt;
}


void
linked_list_append(linked_list_t l, linked_list_element_t k,linked_list_element_t e) 
{
  
  linked_list_link_t cur;	
  assert(l != NULL);

  // To avoid the duplicate key, we remove the key value pair first before we append.
  if (linked_list_key_search(l, k)!=NULL){ 
    linked_list_remove(l, k);
  }

  cur = l->head;
  
  
  /* when l is empty, we need to have it point the newly create link */
  if (cur==NULL){
    l->head = linked_list_new_element(k,e); 
    return;
  }
  
  while (cur->next) {
    cur = cur->next;
  }
  cur->next = linked_list_new_element(k,e);
}


boolean_t
linked_list_remove(linked_list_t l, linked_list_element_t k) 
{
  linked_list_link_t prev, cur, old_head;
	
  assert(l != NULL);
  if (linked_list_is_empty(l))
    return FALSE;

  prev = NULL;
  cur = l->head;
  old_head = l->head;
  
  while(cur){
    if (cur->k==k){//found
      if (prev==NULL){//item found is the first element 
	l->head = cur->next;
      }else{//not the first element
	prev->next = cur-> next;
      }
      free(cur);
      return TRUE;
    }
    prev = cur;
    cur = cur->next;
  }
  return FALSE;
}




boolean_t
linked_list_is_empty(linked_list_t l)
{
  assert(l != NULL);
  return (l->head == NULL);
}


/* private */
static boolean_t
linked_list_count_one(linked_list_element_t k, linked_list_element_t e, linked_list_pfapply_closure_t cl)
{
  int *x = (int*)cl;
  *x = *x + 1;
  return TRUE;
}

int
linked_list_size(linked_list_t l)
{
  int sz = 0;
  linked_list_apply(l, linked_list_count_one, &sz);
  return sz;
}

boolean_t  
linked_list_apply(linked_list_t l, linked_list_pfapply_t pf, linked_list_pfapply_closure_t cl) 
{
  assert(l != NULL && pf != NULL);
  
  if (linked_list_is_empty(l))
    return FALSE;

  linked_list_link_t cur;
  for (cur = l->head; cur; cur = cur->next) {
    if (!pf(cur->k,cur->e, cl))
      break; 
  }
  return TRUE;
}

linked_list_element_t
linked_list_key_search(linked_list_t l, linked_list_element_t k){
  linked_list_link_t cur;
	
  assert(l != NULL);
  if (linked_list_is_empty(l))
    return NULL;

  cur = l->head;
  while(cur){
    if (cur->k==k){
      return cur->e;
    }
    cur = cur->next;
  }
  return NULL;
}

void linked_list_reverse(linked_list_t l)
{
  assert(l!=NULL);
  
  // no need to do anything if size is smile than 2
  if (linked_list_size(l)<2)
    return;
  
  linked_list_link_t cur,prev,next;
  
  // initialize temporary pointers
  prev = NULL;
  cur = l->head;
  next = cur->next;

  while(next){
    cur->next = prev;
    prev = cur;
    cur = next;
    next = next->next;
  }
  // modify the pointer of old tail
  cur->next = prev;
  // have head of l to point to the oldtail
  l->head = cur;
} 

void linked_list_sort(linked_list_t l, linked_list_pfcompare_t pf){
  assert(l!=NULL && pf!=NULL);
  linked_list_link_t cur, one_of_the_rest;
  
  // start with the head
  cur = l->head;
  while(cur->next){
    //compare current with the rest of elements in the linked_list
    one_of_the_rest = cur->next;
    while(one_of_the_rest){
      if (pf(cur->e, one_of_the_rest->e)==1){
	//swap when e1 > e2
	linked_list_element_t temp;
	temp = cur->e;
	cur->e = one_of_the_rest->e;
	one_of_the_rest->e = temp;
      }
      one_of_the_rest = one_of_the_rest->next;
    }
    cur = cur->next;
  }
}
  
